package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

import java.util.ArrayList;
import java.util.List;

import static xyz.scootaloo.oj.ds.helper.CollectionBuilder.list;

/**
 * 动态规划
 * 斐波那契数列
 * @author flutterdash@qq.com
 * @since 2021/3/23 21:55
 */
public class P120 {

    /**
     * RAW        DP               SIZE
     * 2          2                1
     * 3 4        5,  6            2
     * 6 5 7      11, 10, 7        3
     * 4 1 8 3    15, 11, 15, 3    4
     * @param triangle -
     * @return -
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        if (row == 0)
            return 0;
        if (row == 1)
            return triangle.get(0).get(0);

        // 创建一个 dp 数组，为了节省空间，这里一次申请足够所有计算的空间(最下一行，每计算第r行，只使用dp[0~r]的数组空间)
        int[] dp = new int[row];
        dp[0] = triangle.get(0).get(0);
        for (int r = 1; r<row; r++) {
            // 当前行
            List<Integer> currentRow = triangle.get(r);
            /* 每一行的最右边的位置，到这个位置只有一条路径
             * 1          例如
             * 2 3        到达3这个位置，只有 1->3
             * 4 5 6      到达6这个位置，只有 1->3->6
             * 所以每一行最右边的位置，最小路径==triangle[r][r] + dp[r - 1]; // 左上角的位置与当前位置相加
             */
            dp[r] = currentRow.get(r) + dp[r - 1];
            // 从右到左遍历，计算到达当前位置的最小路径
            for (int c = currentRow.size() - 2; c>0; c--) {
                dp[c] = Math.min(dp[c], dp[c - 1]) + currentRow.get(c);
            }
            // 同样，到达当前行的第一个位置也只有一条路径
            dp[0] += currentRow.get(0);
        }

        int min = Integer.MAX_VALUE;
        for (int num : dp)
            if (num < min)
                min = num;
        return min;
    }

    public static void main(String[] args) {
        List<List<Integer>> input_1 = new ArrayList<>();
        input_1.add(list(2));
        input_1.add(list(3, 4));
        input_1.add(list(6, 5, 7));
        input_1.add(list(4, 1, 8, 3));
        List<List<Integer>> input_2 = new ArrayList<>();
        input_2.add(list(-1));
        input_2.add(list(-2, -3));
        List<List<Integer>> input_3 = new ArrayList<>();
        input_3.add(list(-1));              // -1
        input_3.add(list(2, 3));            // 1,  2
        input_3.add(list(1, -1, -3));       // 2, 0, -1

        Tester.createTest(new P120()::minimumTotal)
                .addCase(input_1, 11)
                .addCase(input_2, -4)
                .addCase(input_3, -1)
                .test();
    }

}
